//tinh de quy
#include <stdio.h>
#include <conio.h>
#include <E:\GOOGLE CODE\nienluan\bainienluan\nganxep.cpp>
int GiaiThua(int n);
int Fibo(int f);
int ToHop(int k, int n);
//khu de quy
long GiaiThuaKhuDeQuy(int n);
long FibonaciKhuDeQuy(int n);
int ToHopKhuDeQuy(int n, int k);
main()
{
    int n, k, u, f;
    int ka = 0, kq1 = 0, kq2 = 0;
    printf("--Tinh Giai thua!\n");
    printf("Nhap n: ");
    scanf("%d",&n);
    int kq = GiaiThua(n);
    printf("Giai thua cua %d la: %d",n,kq);
    printf("\nTinh to hop:");
    printf("\nNhap k: ");
    scanf("%d",&k);
    printf("Nhap n: ");
    scanf("%d",&u);
    if(u<k) printf("Loi khi nhap");
    else 
         kq1 = ToHop(k,u);
         printf("\nTo hop chap %d cua %d la: %d\n",k,u,kq1);
    printf("Tim day Fibo!");
    printf("\nNhap so phan tu day Fibo: ");
    scanf("%d",&f);
    printf("Day Fibo tu 1 --> %d la: \n",f);
    if(f<0) printf("Loi khi nhap!");
    else 
    {
         for(int i=0;i<f;i++)
         {
                 int kq2 = Fibo(i);
                 printf("%d  ",kq2);
         }
    }
    //dung ngan xep khu de quy
    int t,y;
    long kq3 = 1; long kq4 = 1;
    printf("\nChuong trinh dung ngan xep de khu de quy!\n");
    printf("Tinh giai thua: ");
    printf("\nNhap n: ");
    scanf("%d",&t);
    if(t<0)        printf("\nLoi khi nhap");
    else
    {
        kq3 = GiaiThuaKhuDeQuy(t);
        printf("Giai thua cua %d la: %ld",t,kq3);
    }
    printf("\nNhap so phan tu day Fibonaci: ");
    scanf("%d",&y);
     printf("Day so Fibo tu 1 --> %d la: \n",y);
    if(y<0)
           printf("\nLoi khi nhap!");
    else
    {
        for(int i=1; i<=y; i++)
        {
                kq4 = FibonaciKhuDeQuy(i);
                printf("%ld  ",kq4);
        }
    }
    int q,p,kq5=1;
    printf("\nTinh to hop: ");
    printf("\nNhap n: ");
    scanf("%d",&q);
    printf("Nhap k: ");
    scanf("%d",&p);
    if(q<p)
           printf("\nLoi khi nhap");
    else
    {
        kq5 = ToHopKhuDeQuy(q,p);
        printf("To hop chap %d cua %d la: %d",p,q,kq5);
    }
    getch();
}
int GiaiThua(int n)
{
    if(n<=0) return 1;
    else return n*GiaiThua(n-1);
}
int Fibo(int f)
{
    if(f==0 || f ==1) return 1;
    else return Fibo(f-1) + Fibo(f-2);
}
int ToHop(int k, int n)
{
    if(k==n) return 1;
    else if(k==1) return n;
    else return ToHop(k,n-1) + ToHop(k-1,n-1);
}
//dung Stack de khu de quy
long GiaiThuaKhuDeQuy(int n)
{
     Stack s;
     MakeNull_Stack(&s);
     if(n == 0 || n == 1)
          return 1;
     else
     {
         while(n != 1)
         {
                 Push(n,&s);
                 n--;
         }
         while(!Empty_Stack(s))
         {
                 n = n*Top(s);
                 Pop(&s);              
         }
     }
     return n;
}
long FibonaciKhuDeQuy(int n)
{
     Stack s;
     int s1, s2, s3;
     MakeNull_Stack(&s);
     if(n == 0 || n == 1) return n;
     else
     {
         Push(n,&s);
         while(n != 0)
         {
                 n--;
                 Push(n, &s);
         }
         if(Top(s) != 2)
         {
                   s2 = Top(s);
                   Pop(&s);
                   s3 = Top(s);
                   Pop(&s);
         }
         while(!Empty_Stack(s))
         {
                               s1 = s2+s3;
                               s2 = s3;
                               s3 = s1;
                               Pop(&s);
         }
     }
     return s1;
}
int ToHopKhuDeQuy(int n, int k)
{
    Stack s;
    MakeNull_Stack(&s);
    int s1 = 1,i=1;
    if(k==n) return 1;
    else if(k==1) return n;
    else
    {
        while(k != 1)
        {
                 Push(k,&s);
                 k--;
        }
        
        if(!Empty_Stack(s))
        {
                for(i=1;i<=k;i++,n--)
                {
                    s1 = s1*n/i;
                    Pop(&s);   
                }        
        }//while(!Empty_Stack(s));
    }
    return s1;
}
